package org.example.myleet.p778;

import java.util.*;

public class Solution {
    /**
     * 76 ms
     */
    public int swimInWater(int[][] grid) {
        //初始化，先将每个点与其右边或下边的点连成具有cost的无向边
        List<Edge> edges = new ArrayList<>();
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[i].length; j++) {
                if (j<grid[i].length-1) {
                    Edge edge = new Edge(new Point(i, j), new Point(i, j + 1), Math.max(grid[i][j], grid[i][j + 1]));
                    edges.add(edge);
                }
                if (i<grid.length-1) {
                    Edge edge = new Edge(new Point(i, j), new Point(i+1, j), Math.max(grid[i][j], grid[i+1][j]));
                    edges.add(edge);
                }
            }
        }
        //然后将这些边按cost排序
        edges.sort(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.time - o2.time;
            }
        });
        //然后从cost最小的边开始连接两个点到并查集中
        UnionFind uf = new UnionFind(new Point(0, 0), new Point(grid.length-1, grid[grid.length-1].length-1));
        for (Edge edge : edges) {
            if (uf.union(edge.p1, edge.p2)) {
                //当并查集中的起始点与终止点连通起来的时候，最后加入的边的cost即为结果
                return edge.time;
            }
        }
        return 0;
    }

    static class UnionFind {
        Map<Point, Point> parent;
        Point start;
        Point end;

        public UnionFind(Point start, Point end) {
            parent = new HashMap<>();
            parent.put(start, start);
            parent.put(end, end);
            this.start = start;
            this.end = end;
        }

        public Point find(Point p) {
            if (!parent.containsKey(p)) {
                parent.put(p, p);
                return p;
            }
            Point p_ = parent.get(p);
            if (!p_.equals(parent.get(p_))) {
                parent.put(p, find(p_));
            }
            return parent.get(p);
        }

        public boolean union(Point p1, Point p2) {
            Point root1 = find(p1);
            Point root2 = find(p2);
            if (!root1.equals(root2)) {
                //连接两个点
                parent.put(root1, root2);
            }
            //检查起始点与结束点的连通性
            Point rootStart = find(start);
            Point rootEnd = find(end);
            if (rootStart.equals(rootEnd)) {
                return true;
            }
            return false;
        }
    }

    static class Edge {
        Point p1;
        Point p2;
        int time;

        public Edge(Point p1, Point p2, int t) {
            
            this.p1 = p1;
            this.p2 = p2;
            this.time = t;
        }
    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x &&
                    y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Point{");
            sb.append("x=").append(x);
            sb.append(", y=").append(y);
            sb.append('}');
            return sb.toString();
        }
    }
}
